#include<iostream>
#include<queue>
using namespace std;
#define null -1

// 二叉树的结点
struct TreeNode
{
	// 结点值（为int类型）
	int val;	
	
	// 左孩子结点指针
	TreeNode *left;
	
	// 右孩子结点指针
	TreeNode *right;
	
	// 构造函数与初始化
	TreeNode() : val(0), left(nullptr), right(nullptr)  {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr)  {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right)  {}
};

// 二叉树root的先序序列化
void LevelSeq(TreeNode* root, vector<int> &s)
{
	// 定义一个队列qu
	queue<TreeNode*> qu;
	
	// 根结点进队
	qu.push(root);
	
	// 队不空循环
	while (!qu.empty())
	{
		// 出队结点p
		TreeNode* p=qu.front(); qu.pop();
		
		// 结点p非空
		if (p!=NULL)
		{
			// 结点值加载进数组
			s.push_back(p->val);
			
			// 左孩子进队（含空的左孩子）
			qu.push(p->left);
			
			// 右孩子进队（含空的右孩子）
			qu.push(p->right);
		}
		
		// 结点p为空
		else
			s.push_back(null); 
	}
}

// 由层次序列化序列s创建二叉链：反序列化
TreeNode* CreateBTree(vector<int> s)	
{
	// 求数组长度
	int n = s.size();
	
	// 长度为0，退出
	if (n==0) return NULL;
	
	// 根结点、辅助指针
	TreeNode* root,*p;
	
	// 用i遍历s
	int i = 0;
	
	// 定义一个队列qu
	queue<TreeNode*> qu;	
	
	// 创建根结点
	root = new TreeNode(s[i++]);	
	
	// 根结点进队 
	qu.push(root);
	
	// 队不空循环：每次循环访问一层结点
	while (!qu.empty())
	{
		// 求队中元素个数
		int cnt=qu.size();
		
		//出队该层的cnt个结点
		for(int j=0; j<cnt; j++)
		{
			// 出队结点p
			p=qu.front(); qu.pop();
			
			// 结点p存在左孩子
			if (i<n && s[i]!=null)
			{
				// 创建结点p的左孩子
				p->left=new TreeNode(s[i++]);
				
				// 左孩子进队
				qu.push(p->left);
			}
			
			// 否则置结点p的左孩子为空
			else
			{
				p->left=NULL;
				i++;
			}
			
			// 结点p存在右孩子
			if (i<n && s[i]!=null)
			{
				// 创建结点p的右孩子
				p->right = new TreeNode(s[i++]);	
				
				// 右孩子进队
				qu.push(p->right);
			}
			
			// 否则置结点p的右孩子为空
			else
			{
				p->right=NULL;
				i++;
			}
		}
	}
	return root;
}

// 输出二叉树括号串 -- 先序遍历
void DispBTree(TreeNode* b)
{
	if (b!=NULL)
	{
		// 输出根结点值
		printf("%d", b->val);
		
		// 存在左右孩子
		if (b->left!=NULL || b->right!=NULL)
		{
			// 有孩子结点时输出"("
			printf("(");
			
			// 递归输出左子树
			DispBTree(b->left);
			
			// 有右孩子结点时输出","
			if (b->right!=NULL)
				printf(",");
			
			// 递归输出右子树
			DispBTree(b->right);
			
			// 输出")"
			printf(")");
		}
	}
}

// 销毁二叉树
void DestroyBTree(TreeNode* &b)
{
	if(b!=NULL)
	{
		// 销毁左子树
		DestroyBTree(b->left);
		
		// 销毁右子树
		DestroyBTree(b->right);
		
		// 销毁根结点
		delete b;
		b=NULL;
	}
}
